import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1630. 等差子数组
 * https://leetcode-cn.com/problems/arithmetic-subarrays/
 */
public class Solutions_1630 {
    public static void main(String[] args) {
        int[] nums = {4, 6, 5, 9, 3, 7};
        int[] l = {0, 0, 2}, r = {2, 3, 5};  // output: {true, false, true}

//        int[] nums = {-12, -9, -3, -12, -6, 15, 20, -25, -20, -15, -10};
//        int[] l = {0, 1, 6, 4, 8, 7}, r = {4, 4, 9, 7, 9, 10};  // output: {false, true, false, false, true, true}

//        int[] nums = {1, 1, 7, 7};
//        int[] l = {0}, r = {3};  // output: {false}

        List<Boolean> result = checkArithmeticSubarrays(nums, l, r);
        System.out.println(result);
    }

    /**
     * 解法二：数学计算法（8ms）
     */
    public static List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> res = new ArrayList<>();
        int len = l.length;
        for (int i = 0; i < len; i++) {
            // 判断 [l[i], r[i]] 区间的子数组，能否构成等差数列
            boolean flag = calc(nums, l[i], r[i]);
            res.add(flag);
        }
        return res;
    }

    public static boolean calc(int[] nums, int l, int j) {
        int len = j - l + 1;
        if (len <= 2) {
            return true;
        }
        // 记录下子数组中的最大值、最小值，便于计算出公差
        int min = nums[l], max = nums[l];
        for (int i = l + 1; i <= j; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        // 子数组可以构成等差数列，并且公差为 0
        if (min == max) {
            return true;
        }
        // 不能整除时，无法构成等差数列
        if ((max - min) % (len - 1) != 0) {
            return false;
        }
        // 计算出公差为 diff
        int diff = (max - min) / (len - 1);
        // 既然公差不为 0，那么不能出现重复的元素，通过 boolean 数组判断某数字是否出现过
        // 防止 {1, 1, 7, 7} = true 的错误情况
        boolean[] visited = new boolean[max - min + 1];
        visited[nums[l] - min] = true;

        for (int i = l + 1; i <= j; i++) {
            int idx = nums[i] - min;
            if (visited[idx] || (nums[i] - nums[l]) % diff != 0) {
                // 子数组中出现了重复的数字，或者 nums[i] 与 nums[l] 的公差不为 diff 时，无法构成等差数列
                return false;
            }
            // 数字标记为出现过
            visited[idx] = true;
        }
        return true;
    }

    /**
     * 解法一：暴力法（22ms）
     */
    public static List<Boolean> checkArithmeticSubarrays2(int[] nums, int[] l, int[] r) {
        List<Boolean> res = new ArrayList<>();
        int len = l.length;
        for (int i = 0; i < len; i++) {
            int arrLen = r[i] - l[i] + 1;
            if (arrLen <= 2) {
                res.add(true);
                continue;
            }
            int[] arr = new int[arrLen];
            // 拷贝子数组
            System.arraycopy(nums, l[i], arr, 0, arrLen);
            boolean flag = check(arr);
            res.add(flag);
        }
        return res;
    }

    // 检查数组是否等差数列
    public static boolean check(int[] arr) {
        Arrays.sort(arr);
        int diff = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        return true;
    }
}
